/*
 * @Author: your name
 * @Date: 2024-05-15 12:52:10
 * @LastEditTime: 2024-05-15 13:09:34
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\332.重新安排行程.cpp
 */
/*
 * @lc app=leetcode.cn id=332 lang=cpp
 *
 * [332] 重新安排行程
 */

// @lc code=start
class Solution {
public:
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    unordered_map<string, map<string, int>>targets;
    bool backtracking(int tickNum, vector<string>&result){
        if(result.size() == tickNum + 1){
            return true;
        }
        for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
            if (target.second > 0 ) { // 记录到达机场是否飞过了
                result.push_back(target.first);
                target.second--;
                if (backtracking(tickNum, result)) return true;
                result.pop_back();
                target.second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;
        for(const vector<string>& vec : tickets){
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK");
        backtracking(tickets.size(), result);
        return result;
    }
};
// @lc code=end

